home *** CD-ROM | disk | FTP | other *** search
/ FishMarket 1.0 / FishMarket v1.0.iso / fishies / 501-525 / disk_519 / avlsort / avl / avl.c next >
C/C++ Source or Header  |  1992-05-06  |  14KB  |  499 lines
  1. /*    avl.c        AVL routines
  2.  
  3.     Copyright 1988 Zinn Computer Company
  4.             by Mark E. Mallett
  5.  
  6.     All rights reserved;
  7.     This software may be used at will, provided that all credits
  8. and style be left in place, and that its distribution is not restricted.
  9. Bug fixes and improvements are welcomed, please send these back to
  10. me at mem@zinn.MV.COM
  11.  
  12.     This is a general-purpose implementation of AVL trees in C.
  13. It is derived from the description of AVL (Adelson-Velskii and Landis)
  14. trees found in Knuth's "The Art of Computer Programming Volume 3:
  15. Searching and Sorting" (Addison-Wesley, 1973) pgs 451-471.
  16.  
  17.     The routines in this file deal with tree maintenance only.
  18. These routines are only concerned with the arrangement of the nodes
  19. in the tree.  Composition of those nodes is left to outside knowledge.
  20. The caller must construct an AVL tree header structure which specifies
  21. routines that deal with nodes (comparison, construction, and deletion).
  22. Please see the attached document for further information.
  23.  
  24. Contained in this file:
  25.  
  26.     avlfind        Find a node in an AVL tree
  27.     avldelete    Delete a node from an AVL tree
  28.     avlinsert    Insert a node into an AVL tree
  29.  
  30. */
  31.  
  32. #include <stdio.h>
  33.  
  34. #include "avl.h"
  35.  
  36.  
  37. /* Local definitions */
  38.  
  39.  
  40. /* External routines */
  41.  
  42.  
  43. /* External data */
  44.  
  45.  
  46. /* Local routines */
  47.  
  48.  
  49. /* Local data */
  50.  
  51. /*
  52.  
  53. *//* avlfind( treeP, keyP )
  54.  
  55.     Lookup a value in an avl tree
  56.  
  57. Accepts :
  58.  
  59.     treeP        Address of the AVLTREE structure describing the tree.
  60.     keyP        Address of a key for the node.  Interpretation of
  61.               the key is left to the "compare key" routine.
  62.  
  63. Returns :
  64.  
  65.     <value>        The address of the node if it is found,
  66.             NULL if it is not.
  67.  
  68.  
  69. */
  70.  
  71. AVLNODE *
  72. avlfind( treeP, keyP )
  73.     AVLTREE        *treeP;        /* Address of the tree struct */
  74.     void        *keyP;        /* Address of the key info */
  75.  
  76. {
  77.     AVLNODE        *nodeP;        /* To follow the tree with */
  78.  
  79.     /* Traverse the tree until the node is found or the tree runs out. */
  80.     for( nodeP = treeP->t_rootP; nodeP != NULL; ) {
  81.     switch( (*treeP->t_cmprtc)( keyP, nodeP ) ) {
  82.         case 0:            /* Node found! */
  83.         return( nodeP );    /* Go ahead and return it */
  84.         
  85.         case -1:            /* Take left branch */
  86.         nodeP = nodeP->n_leftP;
  87.         break;
  88.  
  89.         case 1:            /* Take right branch */
  90.             nodeP = nodeP->n_rightP;
  91.         break;
  92.     }
  93.     }
  94.  
  95.     /* Didn't find the node in the tree. */
  96.     return( NULL );
  97. }
  98. /*
  99.  
  100. *//* avlinsert( treeP, keyP, dataP )
  101.  
  102.     Insert a node in an avl tree
  103.  
  104. Accepts :
  105.  
  106.     treeP        The address of the tree header structure.
  107.     keyP        The address of the key for the node.  Interpretation
  108.               of the key is by the compare and node-create
  109.               routines specified in the avl tree header.
  110.     dataP        The address of the data info for the tree.  The
  111.              interpretation of this is left to the create-node
  112.              routine specified in the avl tree header.
  113.  
  114. Returns :
  115.  
  116.     <value>        -1 if failure of some kind
  117.              0 if successful insertion
  118.              1 if duplicate key
  119.  
  120. Notes:
  121.  
  122.     The tree header structure specifies a node construction routine
  123.     that is responsible for allocating a node and putting the new
  124.     key and data information into it.  It is called as follows:
  125.  
  126.        nodeP = construct( treeP, keyP, dataP, enodeP )
  127.  
  128.     treeP, keyP, and dataP are as passed to this routine.  "enodeP"
  129.     is NULL if a new node is required; otherwise it is the address
  130.     of an already existing node that matches the specified key -
  131.     in this case it is up to the constructor to decide whether to
  132.     overwrite the existing node or to call it an error.  The routine
  133.     is expected to return the address of the AVLNODE structure
  134.     that is allocated (if enode==NULL ) or that exists, or to
  135.     return NULL if the node is not made (or used).
  136.  
  137. */
  138.  
  139. int
  140. avlinsert( treeP, keyP, dataP )
  141.     AVLTREE        *treeP;        /* Addr of the tree struct */
  142.     void        *keyP;        /* The key for insertion insert */
  143.     void        *dataP;        /* The data for the insertion */
  144. {
  145.     int        direction;    /* Direction we took from decision pt */
  146.     AVLNODE        *nodeP;        /* Node that we're looking at */
  147.     AVLNODE        *clearP;    /* For erasing tracks */
  148.     AVLNODE        **nodePP;    /* Pointer to the next link */
  149.     AVLNODE        **topPP;    /* Pointer to the top pointer */
  150.  
  151.     /* Traverse the tree to find an insertion point (or existing key).
  152.        Along the way, we'll adjust the balance counts on the nodes as
  153.        we pass by them.  And as we do this, we'll remember the potential
  154.        tree rotation point (the lowest non-balanced treetop) as well as
  155.        the direction we took from it (in case we have to fix it up when
  156.        we discover a lower balance point). */
  157.  
  158.     nodePP = topPP = &(treeP->t_rootP);    /* Start at top of tree */
  159.     direction = 0;            /* Haven't gone anywhwere yet */
  160.     while( (nodeP = *nodePP) != NULL ) { /* Till we reach the end */
  161.  
  162.     /* See if we're at a potential balance point */
  163.     if ( nodeP->n_balance != 0 ) {
  164.  
  165.         /* New balance point.  Erase any trail we've made to here */
  166.         if ( direction != 0 )
  167.         for( clearP = *topPP; clearP != nodeP;
  168.                  direction = clearP->n_balance ) {
  169.             clearP->n_balance -= direction;
  170.             if ( direction < 0 )
  171.             clearP = clearP->n_leftP;
  172.             else
  173.             clearP = clearP->n_rightP;
  174.         }
  175.          direction = 0;        /* So we make new balance point */
  176.          topPP = nodePP;        /* Remember new top */
  177.     }
  178.  
  179.     /* Now follow the tree... */
  180.     switch( (*treeP->t_cmprtc)( keyP, nodeP ) ) {
  181.         case 0:            /* Match */
  182.         /* Here we have a duplicate node.  First erase the
  183.            trail that we left. */
  184.         if ( direction != 0 )
  185.             for( clearP = *topPP; clearP != NULL;
  186.                 direction = clearP->n_balance ) {
  187.             clearP->n_balance -= direction;
  188.             if ( direction < 0 )
  189.                 clearP = clearP->n_leftP;
  190.             else
  191.                 clearP = clearP->n_rightP;
  192.             }
  193.  
  194.         /* Give the node to the node constructor and
  195.            see what we get. */
  196.         if ( (*treeP->t_mknode)( treeP, keyP, dataP, nodeP ) == NULL )
  197.             return( 1 );    /* Duplicate key */
  198.         return( 0 );        /* Return success */
  199.  
  200.         case -1:            /* Go left */
  201.         nodePP = &(nodeP->n_leftP);
  202.         --nodeP->n_balance;
  203.         if ( direction == 0 )    /* Remember balance point branch? */
  204.             direction = -1;
  205.         break;
  206.  
  207.         case 1:            /* Go right */
  208.         nodePP = &(nodeP->n_rightP);
  209.         ++nodeP->n_balance;
  210.         if ( direction == 0 )
  211.             direction = 1;
  212.         break;
  213.     }
  214.     }
  215.  
  216.     /* Here we've gotten to the bottom, so make a new node */
  217.     nodeP = (*treeP->t_mknode)( treeP, keyP, dataP, (AVLNODE *)NULL );
  218.     if ( nodeP != NULL ) {        /* Successful node creation? */
  219.     nodeP->n_balance = 0;        /* Fill in the nitty gritty */
  220.     nodeP->n_leftP = nodeP->n_rightP = NULL;
  221.     *nodePP = nodeP;        /* Link it in */
  222.     balance( topPP );        /* May need reshaping now */
  223.     return( 0 );            /* Return success */
  224.     }
  225.  
  226.     /* Error making node.  Erase our trail */
  227.     if ( direction != 0 )
  228.     for( clearP = *topPP; clearP != NULL;
  229.             direction = clearP->n_balance ) {
  230.         clearP->n_balance -= direction;
  231.         if ( direction < 0 )
  232.         clearP = clearP->n_leftP;
  233.         else
  234.         clearP = clearP->n_rightP;
  235.     }
  236.     return( -1 );            /* Return error */
  237. }
  238. /*
  239.  
  240. *//* avldelete( treeP, keyP )
  241.  
  242.     Delete a node from an AVL tree
  243.  
  244. Accepts:
  245.  
  246.     treeP        Address of the tree definition structure.
  247.     keyP        Address of the key for the node.  Interpretation
  248.              of the key is left to the key-compare routine
  249.              specified in the tree header.
  250.  
  251. Returns :
  252.  
  253.      <value>        0 if deleted OK
  254.             -1 if not found
  255.  
  256. */
  257.  
  258. int
  259. avldelete( treeP, keyP )
  260.     AVLTREE        *treeP;        /* Addr of tree block */
  261.     void        *keyP;        /* Addr of key */
  262. {
  263.     /* Simply call a local deletion routine */
  264.     if ( delete( treeP, &treeP->t_rootP, keyP ) < 0 )
  265.     return( -1 );            /* error in delete */
  266.     return( 0 );            /* Fine and dandy */
  267. }
  268. /*
  269.  
  270. *//* delete( treeP, topPP, keyP )
  271.  
  272.     Local routine to delete from a subtree
  273.  
  274. Accepts:
  275.  
  276.     treeP        Address of the tree definition structure
  277.     topPP        Address of the pointer to this branch
  278.     keyP        Address of the key for the node.  Interpretation
  279.              of the key is left to the key-compare routine
  280.              specified in the tree header.
  281.  
  282. Returns :
  283.  
  284.      <value>        -1 if not found;
  285.              0 if deleted and tree did not shrink;
  286.              1 if deleted and tree shrunk by 1.
  287.  
  288. */
  289.  
  290. static int
  291. delete( treeP, topPP, keyP )
  292.     AVLTREE        *treeP;        /* Addr of tree block */
  293.     AVLNODE        **topPP;    /* Addr of ptr to branch */
  294.     void        *keyP;        /* Addr of key */
  295. {
  296.     int        i;        /* Scratch */
  297.     int        sts;
  298.     int        cmp;        /* Comparison result */
  299.     AVLNODE        *nodeP;        /* Node pointer */
  300.     AVLNODE        *node1P;    /* Another one */
  301.     AVLNODE        *tempP;        /* For exchanging */
  302.     AVLNODE        **linkPP;    /* Addr of a node pointer */
  303.  
  304.     nodeP = *topPP;            /* Get addr of node */
  305.     if ( nodeP == NULL )        /* If we hit bottom */
  306.     return( -1 );            /*  then we didn't find it */
  307.  
  308.     cmp = (*treeP->t_cmprtc)( keyP, nodeP );
  309.     if ( cmp == 0 ) {
  310.     /* We've found the node to delete.  If it has no children we
  311.        can just get rid of it.  Otherwise we have to remove it
  312.        from the tree somehow.  If one or the other subtrees
  313.         is empty, then it is easy. */
  314.  
  315.     if ( nodeP->n_leftP == NULL ) {
  316.         /* Just shorten the right branch (even if it doesn't exist) */
  317.         *topPP = nodeP->n_rightP;
  318.         (*treeP->t_rmnode)( treeP, nodeP );
  319.         return( 1 );        /* Branch shrunk */
  320.     }
  321.  
  322.     if ( nodeP->n_rightP == NULL ) {
  323.         /* Shorten the left branch */
  324.         *topPP = nodeP->n_leftP;
  325.         (*treeP->t_rmnode)( treeP, nodeP );
  326.         return( 1 );
  327.     }
  328.  
  329.     /* Both subtrees exist.  Exchange this node with the one
  330.        logically adjacent (in value) to it.  Then this node
  331.        will be at the end of a branch and we can recurse to
  332.        delete it. */
  333.  
  334.     if( nodeP->n_balance < 0 ) {
  335.         node1P = nodeP->n_leftP;
  336.         linkPP = &(node1P->n_leftP);
  337.         for( ; node1P->n_rightP != NULL; node1P = node1P->n_rightP )
  338.         linkPP = &(node1P->n_rightP);
  339.         cmp = -1;            /* We went left */
  340.     } else {
  341.         node1P = nodeP->n_rightP;
  342.         linkPP = &(node1P->n_rightP);
  343.         for( ; node1P->n_leftP != NULL; node1P = node1P->n_leftP )
  344.         linkPP = &(node1P->n_leftP);
  345.         cmp = 1;            /* We're going right */
  346.     }
  347.  
  348.     /* Exchange the two nodes.  We have to actually exchange by
  349.        relinking rather than copying since the node may imply
  350.        other stuff that we don't know about here. */
  351.  
  352.     tempP = node1P->n_rightP;    /* Exchange right pointers */
  353.     node1P->n_rightP = nodeP->n_rightP;
  354.     nodeP->n_rightP = tempP;
  355.  
  356.     tempP = node1P->n_leftP;    /* Exchange left pointers */
  357.     node1P->n_leftP = nodeP->n_leftP;
  358.     nodeP->n_leftP = tempP;
  359.  
  360.     i = node1P->n_balance;        /* Exchange balance values */
  361.     node1P->n_balance = nodeP->n_balance;
  362.     nodeP->n_balance = i;
  363.  
  364.     *topPP = node1P;        /* Exchange the nodes */
  365.     *linkPP = nodeP;
  366.     nodeP = node1P;            /* Pretend we're here */
  367.     }
  368.  
  369.     /* Remove the node from left or right subtree depending on "cmp" */
  370.     switch ( cmp ) {
  371.     case -1:
  372.         sts = delete( treeP, &nodeP->n_leftP, keyP );
  373.         if ( sts == 1 )        /* If it shrunk */
  374.         ++nodeP->n_balance;    /*  reflect that in the balance */
  375.         break;
  376.  
  377.     case 1:
  378.         sts = delete( treeP, &nodeP->n_rightP, keyP );
  379.         if ( sts == 1 )        /* Right branch shrunk? */
  380.         --nodeP->n_balance;    /*  adjust the balance */
  381.         break;
  382.     }
  383.  
  384.     if ( sts == 1 )            /* If we changed balance */
  385.     if ( nodeP->n_balance != 0 )    /*  if it's 0 it shrunk but is ok */
  386.         sts = balance( topPP );    /*    otherwise fix it up */
  387.     return( sts );
  388. }
  389. /*
  390.  
  391. *//* balance( branchPP )
  392.  
  393.     Local routine to balance a branch
  394.  
  395. Accepts :
  396.  
  397.     branchPP    Addr of the variable pointing to the top n
  398.  
  399. Returns :
  400.  
  401.     <value>        0 if branch has stayed the same height;
  402.             1 if branch shrunk by one.
  403.  
  404.  
  405. Notes :
  406.  
  407.     This routine accepts a branch in conditions left by the
  408. internal routines only.  No other cases are dealt with.
  409.  
  410. */
  411.  
  412. static int
  413. balance( branchPP )
  414.     AVLNODE        **branchPP;    /* Ptr to top node */
  415. {
  416.     int        shrunk;        /* Whether we shrunk */
  417.     AVLNODE        *nodeP;        /* Current top node */
  418.     AVLNODE        *leftP;        /* Left child */
  419.     AVLNODE        *rightP;    /* Right child */
  420.     AVLNODE        *migP;        /* A ndoe that migrates */
  421.  
  422.     /* Pick up relevant information */
  423.     nodeP = *branchPP;
  424.     leftP = nodeP->n_leftP;
  425.     rightP = nodeP->n_rightP;
  426.     shrunk = 0;                /* Assume tree doesn't shrink */
  427.  
  428.     /* Process according to out-of-balance amount, if any */
  429.     switch( nodeP->n_balance ) {
  430.     case -2:            /* Too heavy on left */
  431.         if ( leftP->n_balance <= 0 ) {
  432.  
  433.         /* Single rotation */
  434.         *branchPP = leftP;
  435.         nodeP->n_leftP = leftP->n_rightP;
  436.         leftP->n_rightP = nodeP;
  437.         ++leftP->n_balance;
  438.         nodeP->n_balance = -(leftP->n_balance);
  439.         if ( leftP->n_balance == 0 )
  440.             shrunk = 1;
  441.         }
  442.         else {            /* Migration of inner node to top */
  443.         migP = leftP->n_rightP;
  444.         leftP->n_rightP = migP->n_leftP;
  445.         nodeP->n_leftP = migP->n_rightP;
  446.         migP->n_leftP = leftP;
  447.         migP->n_rightP = nodeP;
  448.         *branchPP = migP;
  449.         if ( migP->n_balance < 0 ) {
  450.             leftP->n_balance = 0;
  451.             nodeP->n_balance = 1;
  452.         }
  453.         else if ( migP->n_balance > 0 ) {
  454.             leftP->n_balance = -1;
  455.             nodeP->n_balance = 0;
  456.         }
  457.         else
  458.             leftP->n_balance = nodeP->n_balance = 0;
  459.         migP->n_balance = 0;
  460.         shrunk = 1;
  461.         }
  462.         break;
  463.             
  464.     case  2:            /* Too heavy on right */
  465.         if ( rightP->n_balance >= 0 ) {
  466.  
  467.         /* Single rotation */
  468.         *branchPP = rightP;
  469.         nodeP->n_rightP = rightP->n_leftP;
  470.         rightP->n_leftP = nodeP;
  471.         --rightP->n_balance;
  472.         nodeP->n_balance = -(rightP->n_balance);
  473.         if ( rightP->n_balance == 0 )
  474.             shrunk = 1;
  475.         }
  476.         else {            /* Migration of inner node */
  477.         migP = rightP->n_leftP;
  478.         rightP->n_leftP = migP->n_rightP;
  479.         nodeP->n_rightP = migP->n_leftP;
  480.         migP->n_leftP = nodeP;
  481.         migP->n_rightP = rightP;
  482.         *branchPP = migP;
  483.         if ( migP->n_balance < 0 ) {
  484.             nodeP->n_balance = 0;
  485.             rightP->n_balance = 1;
  486.         }
  487.         else if ( migP->n_balance > 0 ) {
  488.             nodeP->n_balance = -1;
  489.             rightP->n_balance = 0;
  490.         }
  491.         else
  492.             nodeP->n_balance = rightP->n_balance = 0;
  493.         migP->n_balance = 0;
  494.         shrunk = 1;
  495.         }
  496.     }
  497.     return( shrunk );
  498. }
  499.